/*
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 * TopDownConstructor.java
 * Copyright (C) 2007-2012 University of Waikato, Hamilton, New Zealand
 */

package weka.core.neighboursearch.balltrees;

import java.util.Collections;
import java.util.Enumeration;
import java.util.Vector;

import weka.core.EuclideanDistance;
import weka.core.Instance;
import weka.core.Option;
import weka.core.TechnicalInformation;
import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformation.Type;
import weka.core.TechnicalInformationHandler;
import weka.core.Utils;

/**
 * <!-- globalinfo-start --> The class implementing the TopDown construction
 * method of ball trees. It further uses one of a number of different splitting
 * methods to split a ball while constructing the tree top down.<br/>
 * <br/>
 * For more information see also:<br/>
 * <br/>
 * Stephen M. Omohundro (1989). Five Balltree Construction Algorithms.
 * <p/>
 * <!-- globalinfo-end -->
 * 
 * <!-- technical-bibtex-start --> BibTeX:
 * 
 * <pre>
 * &#64;techreport{Omohundro1989,
 *    author = {Stephen M. Omohundro},
 *    institution = {International Computer Science Institute},
 *    month = {December},
 *    number = {TR-89-063},
 *    title = {Five Balltree Construction Algorithms},
 *    year = {1989}
 * }
 * </pre>
 * <p/>
 * <!-- technical-bibtex-end -->
 * 
 * <!-- options-start --> Valid options are:
 * <p/>
 * 
 * <pre>
 * -S &lt;classname and options&gt;
 *  Ball splitting algorithm to use.
 * </pre>
 * 
 * <!-- options-end -->
 * 
 * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
 * @version $Revision$
 */
public class TopDownConstructor extends BallTreeConstructor implements TechnicalInformationHandler {

    /** for serialization. */
    private static final long serialVersionUID = -5150140645091889979L;

    /**
     * The BallSplitter algorithm used by the TopDown BallTree constructor, if it is
     * selected.
     */
    protected BallSplitter m_Splitter = new PointsClosestToFurthestChildren();

    /**
     * Creates a new instance of TopDownConstructor.
     */
    public TopDownConstructor() {
    }

    /**
     * Returns a string describing this nearest neighbour search algorithm.
     * 
     * @return a description of the algorithm for displaying in the
     *         explorer/experimenter gui
     */
    public String globalInfo() {
        return "The class implementing the TopDown construction method of " + "ball trees. It further uses one of a number of different splitting " + "methods to split a ball while constructing the tree top down.\n\n" + "For more information see also:\n\n" + getTechnicalInformation().toString();
    }

    /**
     * Returns an instance of a TechnicalInformation object, containing detailed
     * information about the technical background of this class, e.g., paper
     * reference or book this class is based on.
     * 
     * @return the technical information about this class
     */
    @Override
    public TechnicalInformation getTechnicalInformation() {
        TechnicalInformation result;

        result = new TechnicalInformation(Type.TECHREPORT);
        result.setValue(Field.AUTHOR, "Stephen M. Omohundro");
        result.setValue(Field.YEAR, "1989");
        result.setValue(Field.TITLE, "Five Balltree Construction Algorithms");
        result.setValue(Field.MONTH, "December");
        result.setValue(Field.NUMBER, "TR-89-063");
        result.setValue(Field.INSTITUTION, "International Computer Science Institute");

        return result;
    }

    /**
     * Builds the ball tree top down.
     * 
     * @return The root node of the tree.
     * @throws Exception If there is problem building the tree.
     */
    @Override
    public BallNode buildTree() throws Exception {
        BallNode root;

        m_NumNodes = m_MaxDepth = 0;
        m_NumLeaves = 1;

        m_Splitter.setInstances(m_Instances);
        m_Splitter.setInstanceList(m_InstList);
        m_Splitter.setEuclideanDistanceFunction((EuclideanDistance) m_DistanceFunction);

        root = new BallNode(0, m_InstList.length - 1, 0);
        root.setPivot(BallNode.calcCentroidPivot(m_InstList, m_Instances));
        root.setRadius(BallNode.calcRadius(m_InstList, m_Instances, root.getPivot(), m_DistanceFunction));

        splitNodes(root, m_MaxDepth + 1, root.m_Radius);

        return root;
    }

    /**
     * Recursively splits nodes of a ball tree until <=m_MaxInstancesInLeaf
     * instances remain in a node.
     * 
     * @param node       The node to split.
     * @param depth      The depth of this node in the tree, so that m_MaxDepth is
     *                   correctly updated.
     * @param rootRadius The smallest ball enclosing all the data points.
     * @throws Exception If there is some problem in splitting.
     */
    protected void splitNodes(BallNode node, int depth, final double rootRadius) throws Exception {

        if (node.m_NumInstances <= m_MaxInstancesInLeaf || (rootRadius == 0 ? true : node.m_Radius / rootRadius < m_MaxRelLeafRadius)) {
            return;
        }

        m_NumLeaves--;
        m_Splitter.splitNode(node, m_NumNodes);
        m_NumNodes += 2;
        m_NumLeaves += 2;

        if (m_MaxDepth < depth) {
            m_MaxDepth = depth;
        }

        splitNodes(node.m_Left, depth + 1, rootRadius);
        splitNodes(node.m_Right, depth + 1, rootRadius);

        if (m_FullyContainChildBalls) {
            double radius = BallNode.calcRadius(node.m_Left, node.m_Right, node.getPivot(), m_DistanceFunction);
            // The line that follows was commented out by Eibe because it does not
            // have any effect
            // Instance pivot = BallNode.calcPivot(node.m_Left, node.m_Right,
            // m_Instances);
            // System.err.println("Left Radius: "+node.m_Left.getRadius()+
            // " Right Radius: "+node.m_Right.getRadius()+
            // " d(p1,p2): "+
            // m_DistanceFunction.distance(node.m_Left.getPivot(),
            // node.m_Right.getPivot())+
            // " node's old radius: "+node.getRadius()+
            // " node's new Radius: "+radius+
            // " node;s old pivot: "+node.getPivot()+
            // " node's new pivot: "+pivot);
            node.setRadius(radius);
        }
    }

    /**
     * Adds an instance to the ball tree.
     * 
     * @param node The root node of the tree.
     * @param inst The instance to add to the tree.
     * @return The new master index array after adding the instance.
     * @throws Exception If there is some problem adding the given instance to the
     *                   tree.
     */
    @Override
    public int[] addInstance(BallNode node, Instance inst) throws Exception {

        double leftDist, rightDist;

        if (node.m_Left != null && node.m_Right != null) { // if node is not a leaf
            // go further down the tree to look for the leaf the instance should be in

            leftDist = m_DistanceFunction.distance(inst, node.m_Left.getPivot(), Double.POSITIVE_INFINITY); // instance.value(m_SplitDim);
            rightDist = m_DistanceFunction.distance(inst, node.m_Right.getPivot(), Double.POSITIVE_INFINITY);
            if (leftDist < rightDist) {
                addInstance(node.m_Left, inst);
                // go into right branch to correct instance list boundaries
                processNodesAfterAddInstance(node.m_Right);
            } else {
                addInstance(node.m_Right, inst);
            }
            // correct end index of instance list of this node
            node.m_End++;
        } else if (node.m_Left != null || node.m_Right != null) {
            throw new Exception("Error: Only one leaf of the built ball tree is " + "assigned. Please check code.");
        } else { // found the leaf to insert instance

            int index = m_Instances.numInstances() - 1;

            int instList[] = new int[m_Instances.numInstances()];
            System.arraycopy(m_InstList, 0, instList, 0, node.m_End + 1);
            if (node.m_End < m_InstList.length - 1) {
                System.arraycopy(m_InstList, node.m_End + 2, instList, node.m_End + 2, m_InstList.length - node.m_End - 1);
            }
            instList[node.m_End + 1] = index;
            node.m_End++;
            node.m_NumInstances++;
            m_InstList = instList;

            m_Splitter.setInstanceList(m_InstList);

            if (node.m_NumInstances > m_MaxInstancesInLeaf) {
                m_Splitter.splitNode(node, m_NumNodes);
                m_NumNodes += 2;
            }
        }
        return m_InstList;
    }

    /**
     * Post process method to correct the start and end indices of BallNodes on the
     * right of the node where the instance was added.
     * 
     * @param node The node whose m_Start and m_End need to be updated.
     */
    protected void processNodesAfterAddInstance(BallNode node) {
        // updating start and end indices for the node
        node.m_Start++;
        node.m_End++;
        // processing child nodes
        if (node.m_Left != null && node.m_Right != null) {
            processNodesAfterAddInstance(node.m_Left);
            processNodesAfterAddInstance(node.m_Right);
        }
    }

    /**
     * Returns the tip text for this property.
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String ballSplitterTipText() {
        return "The BallSplitter algorithm set that would be used by the TopDown " + "BallTree constructor.";
    }

    /**
     * Returns the BallSplitter algorithm set that would be used by the TopDown
     * BallTree constructor.
     * 
     * @return The BallSplitter currently in use.
     */
    public BallSplitter getBallSplitter() {
        return m_Splitter;
    }

    /**
     * Sets the ball splitting algorithm to be used by the TopDown constructor.
     * 
     * @param splitter The BallSplitter to use.
     */
    public void setBallSplitter(BallSplitter splitter) {
        m_Splitter = splitter;
    }

    /**
     * Returns an enumeration describing the available options.
     * 
     * @return an enumeration of all the available options.
     */
    @Override
    public Enumeration<Option> listOptions() {
        Vector<Option> newVector = new Vector<Option>();

        newVector.addElement(new Option("\tBall splitting algorithm to use.", "S", 1, "-S <classname and options>"));

        newVector.addAll(Collections.list(super.listOptions()));

        return newVector.elements();
    }

    /**
     * Parses a given list of options.
     * 
     * <!-- options-start --> Valid options are:
     * <p/>
     * 
     * <pre>
     * -S &lt;classname and options&gt;
     *  Ball splitting algorithm to use.
     * </pre>
     * 
     * <!-- options-end -->
     * 
     * @param options the list of options as an array of strings
     * @throws Exception if an option is not supported
     */
    @Override
    public void setOptions(String[] options) throws Exception {

        String optionString = Utils.getOption('S', options);
        if (optionString.length() != 0) {
            String nnSearchClassSpec[] = Utils.splitOptions(optionString);
            if (nnSearchClassSpec.length == 0) {
                throw new Exception("Invalid BallSplitter specification string.");
            }
            String className = nnSearchClassSpec[0];
            nnSearchClassSpec[0] = "";

            setBallSplitter((BallSplitter) Utils.forName(BallSplitter.class, className, nnSearchClassSpec));
        } else {
            setBallSplitter(new PointsClosestToFurthestChildren());
        }

        super.setOptions(options);

    }

    /**
     * Gets the current settings of KDtree.
     * 
     * @return an array of strings suitable for passing to setOptions
     */
    @Override
    public String[] getOptions() {
        Vector<String> result = new Vector<String>();

        result.add("-S");
        result.add(m_Splitter.getClass().getName());

        Collections.addAll(result, super.getOptions());

        return result.toArray(new String[result.size()]);
    }

}
